package taller2.model.graph.algorithms;

import java.util.ArrayList;
import java.util.Collection;

import taller2.interfaces.Connection;
import taller2.interfaces.EndNodeApplicator;
import taller2.interfaces.Graph;
import taller2.interfaces.InitialNodeApplicator;
import taller2.interfaces.Node;
import taller2.utils.Constants;
import taller2.utils.Constants.Colores;

public class FordFulkersonApplicator extends AlgorithmApplicatorImpl implements InitialNodeApplicator,EndNodeApplicator{
	private int startId,endId;
	private static final String path = Constants.savedGraphsPath + "FordFulkerson";
    private Node source;
    private Node sink;
    private Collection<Node> visited;
    private Collection<Connection> route;
    private Collection<Connection> reversedConnections;
    private Node visiting;
    private int count;
    private boolean directed;
    
	public FordFulkersonApplicator(){
		super();
		startId = -1;
		endId = -1;
        source = sink = null;
        directed = false;
	}
	
	// applies the algorithm to the graph
	// and stores the path's and pseudocode lines
	public void solveProblem(Graph g){
		
		if(noGraph(g) || !noGraphPaths() || !noPseudocodeLines())
			return;

		g.unselectConnections();
        g.unselectNodes();
        g.killWeights();
        directed = g.isDirected();

        
        count = 0;
        g.save(path);
        save(g,0);
        
        ArrayList<Node> nodes = g.getNodes();
        if(startId != -1)
            source = g.getNodeByIndex(startId);
        else
            source = nodes.get(0);

        if(endId != -1)
            sink = g.getNodeByIndex(endId);
        else
            sink = nodes.get(nodes.size()-1);

        source.changeColor(Constants.Colores.purple);
        sink.changeColor(Constants.Colores.green);

        ArrayList<Node> intermedios = new ArrayList<Node>(g.getNodes());
        intermedios.remove(source);
        intermedios.remove(sink);


        save(g,3);

/*
        Collection<Connection> connections = g.getAllConnections().values();
		for(Connection connection : connections) {
            connection.setFlux(0);
            connection.setCapacity(connection.getWeight());
            connection.select();
            connection.setWeight(Constants.ConnectionKilled);
            save(g,4);
            connection.unselect();
        }
*/
        save(g,6);



        visited = new ArrayList<Node>();
        route = new ArrayList<Connection>();
        reversedConnections = new ArrayList<Connection>();
        visiting = source;
        while (recursivaloca(g)) {
            int minResidualFlux = 999999999;
            for (Connection connection : route) {
                int residualFlux;
                if(!reversedConnections.contains(connection))
                    residualFlux = flujoResidual(connection.getThisNode(), connection.getOtherNode());
                else
                    residualFlux = connection.getFlux();
                if (minResidualFlux > residualFlux)
                    minResidualFlux = residualFlux;
                connection.select();
            }
            save(g,8);
            for (Connection connection : route) {
                if (!reversedConnections.contains(connection))
                    connection.setFlux(connection.getFlux() + minResidualFlux);
                else
                    connection.setFlux(connection.getFlux() - minResidualFlux);
                save(g,9);
            }

            save(g,6);
            visited = new ArrayList<Node>();
            route = new ArrayList<Connection>();
            reversedConnections = new ArrayList<Connection>();
            visiting = source;
            g.unselectConnections();
        }

        source.changeColor(Colores.purple);
        sink.changeColor(Colores.green);        
        save(g,10);
        save(g,10);

        g.load(path);
	}

    private boolean recursivaloca(Graph g) {
        Node visitingHere = visiting;
        if (visiting == sink) {
            sink.unselect();
            sink.changeColor(Constants.Colores.green);
            return true;
        }
        visited.add(visiting);
        visitingHere.select();
        save(g,6);
        for(Connection connection : visiting.getConnections()){
            connection.select();
            save(g,6);
            Node next = connection.getOtherNode();
            if (!visited.contains(next) && flujoResidual(visitingHere,next) > 0 ) {
                next.select();
                visitingHere.unselect();
                source.changeColor(Constants.Colores.purple);
                visited.add(visitingHere);
                visiting = next;
                route.add(connection);
                if (recursivaloca(g)) {
                    return true;
                }
                else {
                    route.remove(connection);
                    connection.unselect();
                    save(g, 6);
                }
            }else{
                source.changeColor(Constants.Colores.purple);
                if (!reversedConnections.contains(connection))
                connection.unselect();
                save(g, 6);
            }
        }
        for (Connection connection : g.getConnectionsTo(visitingHere)){
            if (isReversedConection(connection)){
                connection.select();
                visitingHere.unselect();
                visited.add(visitingHere);
                visiting = connection.getThisNode();
                reversedConnections.add(connection);
                route.add(connection);
                if (recursivaloca(g))
                    return true;
                else {
                    route.remove(connection);
                    reversedConnections.remove(connection);
                    connection.unselect();
                    save(g, 6);
                }
            }
        }
        visitingHere.unselect();
        return false;
    }

    private boolean isReversedConection(Connection connection) {
        return (connection.getOtherNode().getConnectionTo(connection.getThisNode()) == null
                && !visited.contains(connection.getThisNode())
                && connection.getFlux()>0);
    }

    private int capacidad(Node origin, Node destiny){
        Connection c = origin.getConnectionTo(destiny);
        if(c == null)
            return 0;
        else
            return c.getCapacity();
    }

    private void save(Graph g, int codeLine){
        pseudocodeLines.add(codeLine);
        saveGraph(g,path+count);
        count++;
    }

    private int flujo(Node origin, Node destiny){
        Connection c1 = origin.getConnectionTo(destiny);
        Connection c2 = destiny.getConnectionTo(origin);
        int ida = 0;
        int vuelta = 0;
        if (c1 != null) ida = c1.getFlux();
        if (c2 != null) vuelta = c2.getFlux();
        return ida-vuelta;
    }

    private int flujoResidual(Node origin, Node destiny){
        return capacidad(origin,destiny) - flujo(origin,destiny);
    }
	
	public void save(String path){
	};

	public void load(String path){
	}

	@Override
	public int getHighlightedWordNumber() {
		return -1;
	}

	@Override
	public void setEndNode(int selectedNode) {
		endId = selectedNode;
	}

	@Override
	public void setInitialNode(int selectedNode) {
		startId = selectedNode;
	}

	public String getStartingGraphPath() {
		if(graphPaths.isEmpty())
			return "";
		
		return graphPaths.get(0);
	}

	public boolean wasDirected() {
		return directed;
	}

	public String getSolGraphPath() {
		if(graphPaths.isEmpty())
			return "";
		int cant = graphPaths.size();
		return graphPaths.get(cant-1);
	}
}
